/**
 * Created with JetBrains PhpStorm.
 * User: ishowshao
 * Date: 12-8-20
 * Time: 下午8:49
 */
Array.prototype.mergeSort = function () {
    var merge = function (array, first, mid, last) {
        var tmp = [];
        var i = first;
        var j = mid + 1;
        while (i <= mid && j <= last) {
            if (array[i] < array[j]) {
                tmp.push(array[i]);
                i++;
            } else {
                tmp.push(array[j]);
                j++;
            }
        }
        while (i <= mid) {
            tmp.push(array[i]);
            i++;
        }
        while (j <= last) {
            tmp.push(array[j]);
            j++;
        }
        for (var l = 0, length = tmp.length; l < length; l++) {
            array[first + l] = tmp[l];
        }
    };
    var sort = function (array, i, j) {
        if (i < j) {
            var mid = Math.floor((i + j) / 2);
            sort(array, i, mid);
            sort(array, mid + 1, j);
            merge(array, i, mid, j);
        }
    };
    sort(this, 0, this.length - 1);
};

//以下为测试代码
var array = [];
for (var x = 0; x < 1000000; x++) {
    array.push(x + 1);
}
function shuffle() {
    return Math.random() - 0.5;
}
array.sort(shuffle);
array.sort(shuffle);

//console.log(array.join(','));
//var array2 = [];
//for (var i = 0; i < array.length; i++) {
//    array2.push(array[i]);
//}

var st = +new Date();
//array2.sort(function (a, b) {
//    return a > b;
//});
//console.log(+new Date() - st);
//document.writeln(+new Date() - st);

st = +new Date();
//console.log(st);
array.mergeSort();
//console.log(+new Date() - st);
document.writeln(+new Date() - st);
//document.writeln(array.join(','));

